// 请考虑一颗二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。

// 举个例子，如上图所示，给定一颗叶值序列为 (6, 7, 4, 9, 8) 的树。

// 如果有两颗二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。

// 如果给定的两个头结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。

// 提示：

// 	给定的两颗树可能会有 1 到 100 个结点。

#include <vector>

using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 前序遍历

class Solution {
public:
    bool leafSimilar(TreeNode* root1, TreeNode* root2) {
        vector<int> leaf1{};
        vector<int> leaf2{};
        func(root1, leaf1);
        func(root2, leaf2);
        return leaf1 == leaf2;
    }
    void func(TreeNode* node, vector<int>& leaf) {
        if (!node) return;
        if (!node->left && !node->right) {
            leaf.push_back(node->val);
        }
        func(node->left, leaf);
        func(node->right, leaf);
    }
};
